package two;

import java.util.Scanner;

public class test10302 {
    private static long[][] flag;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n   = scanner.nextInt();
        flag = new long[n + 1][n + 1];
        long m = f(n, log(n));
        System.out.println(m % 1000000000);
    }

    private static long f(int n, int k) {
        long sum = 0;
        if (flag[n][k] != 0) {
            return flag[n][k];
        }

        if (k == 0) {
            return 1;
        } else if (n == 0) {
            return 1;
        } else if (k > log(n)) {
            return f(n, log(n));
        } else if (k > 0) {
            for (int i = 0; i <= k; i++) {
                sum = f((int) (n - Math.pow(2, i)), i) + sum;
            }
        }
        flag[n][k] = sum;
        return sum;
    }

    private static int log(int n) {
        return (int) (Math.log(n) / Math.log(2));
    }
}
